package code;

import java.util.HashSet;
import java.util.Set;

public class RemoveDuplicates {
	 static public class ListNode {
		      int val;
		     ListNode next;
		     ListNode(int x) {
		          val = x;
		          next = null;
		      }
		  }
    public ListNode deleteDuplicates(ListNode head) {
        ListNode p,pre,pre2;
        pre=p=head;
        
        if(head==null || head.next==null)	return head;
        Set<Integer> vis=new HashSet<Integer>();
        
        while(p!=null){
        	pre=p;
        	p=p.next;
        	if(p==null)	break;
        	if(p.val==pre.val){
        		pre.next=p.next;
        		p=p.next;
        		vis.add(pre.val);
        	}
        }
        p=head;
        pre=null;
        head=null;
        while(p!=null){
        	if(vis.contains(p.val)){
        		if(pre!=null){
        			pre.next=p.next;
        		}
        		p=p.next;
        	}
        	else {
        		if(pre==null)	{
        			head=p;
        		}
        		pre=p;
        		p=p.next;
        	}
        }
        p=head;
        while(p!=null){
        	System.out.print(p.val+" ");
        	p=p.next;
        }
        System.out.println();
    	return head;
    }
    
	public static void main(String[] args){
		ListNode a=new ListNode(1);
		ListNode b=new ListNode(1);
		ListNode c=new ListNode(3);
		ListNode d=new ListNode(3);
		ListNode e=new ListNode(4);
		ListNode f=new ListNode(4);
//		ListNode g=new ListNode(5);
		a.next=b;
		b.next=c;
		c.next=d;
		d.next=e;
		e.next=f;
//		f.next=g;
		
		RemoveDuplicates rd=new RemoveDuplicates();
		rd.deleteDuplicates(a);
	}
}
